


public class EncodageHuffman {

	// alphabet size of extended ASCII
    private static final int R = 256;
    private String tab[];
    private char chartab[];
    
	
	public String EncodagesemiAdaptatif (String s){
		
		//tabulage frequence
		char[] input = s.toCharArray();
		int[] freq = new int[R];
		for (int i = 0; i < input.length; i++){
            freq[input[i]]++;
            
		}			

		//construction list ordonnee par frequence decroissante
		BinaryHeap bh = new BinaryHeap();
		NodeTree array[]= new NodeTree[R];
		
		for (int i = 0; i < R; i++){
			if(freq[i]>0){
				char  c = (char) i;
				NodeTree e = new NodeTree(freq[i],c);
				array[i]=e;
				bh.insert(e);
			}
		}
		int size=bh.size();
		
		//verification
		/*System.out.println("size="+size+"\n");
		for(int i=0;i<R;i++){
			if(array[i]!=null)
			System.out.println("c="+array[i].getC()+" f="+array[i].getFreq());
		}
		System.out.println("");*/
		
		
		//restructuration arbre
		while(bh.size()!=1){
			NodeTree e1=(NodeTree) bh.deleteMin();
			NodeTree e2=(NodeTree) bh.deleteMin();
			int f=e1.getFreq()+e2.getFreq();
			NodeTree e= new NodeTree(f,(char) 12);
			e.setLeft(e1);
			e.setRight(e2);
			e1.setParent(e);
			e2.setParent(e);
			bh.insert(e);
			//verification
			//System.out.println("c="+e1.getC()+" f="+e1.getFreq());
			//System.out.println("c="+e2.getC()+" f="+e2.getFreq()+"\n");
		}
		
		//creation du code
		tab=new String[size];
		chartab= new char[size];
		
		int a=0;
		for(int i=0;i<R;i++){
			NodeTree e= array[i];
			if(e!=null){
				chartab[a]=e.getC();
				tab[a]=getpath(e);
				//System.out.println("path="+tab[a]+" c="+e.getC()+" f="+e.getFreq());
				a++;
			}
		}
		
		//creation du string encode
		String code="";
		for(int i=0;i<s.length();i++){
			char c=s.charAt(i);
			for(int j=0;j<chartab.length;j++){
				if(c==chartab[j]){
					code+=tab[j];
				}
			}
		}
		
		System.out.println(code);
		return code;
		
	}
	
	public String getpath(NodeTree e1) {
		String path="";
		while (e1!=null){
			if (e1.getParent()!=null){
				if(e1.getParent().getLeft()==e1) {path+="0";}
				if(e1.getParent().getRight()==e1) {path+="1";}
			}
			e1=e1.getParent();
		}
		return flip(path);
	}

	private String flip(String path) {
		String h="";
		for(int i=path.length()-1;i>=0;i--){
			h+=path.charAt(i);
		}
		return h;
	}

	public String generateTable(){

		String Table="";
		for(int i=0;i<chartab.length;i++){
			Table+=chartab[i]+tab[i];
		}
		
		
		return Table;
	}
	
}
